/*
 * GreedyBestFirstSearch.java
 * 
 * TCSS 435 - Autumn 2012
 * Homework 2
 */

import java.util.*;

/**
 * A greedy best first search.
 * 
 * @author Dallas Rosson
 * @author Dr. Matthew Alden
 * @version Autumn 2012
 */
public class GreedyBestFirstSearch {
	
	private static class Node implements Comparable<Node> {
		
		public StateWithHeuristic state;
		public double pathCost;
		public Node parent;
		public double trueCost;

		public Node(StateWithHeuristic state, Node parent, StateWithHeuristic goal, Double trueCost) {
						
			this.state = state;
			this.pathCost = state.getEstimatedCostToGoal(goal);
			this.parent = parent;
			this.trueCost = trueCost;
			
		}

		public boolean equals(Object obj) {
			
			return state.equals(((Node)obj).state);
			
		}

		public int hashCode() {
			
			return state.hashCode();
			
		}

		public int compareTo(Node node) {
			
			if (pathCost < node.pathCost)
				return -1;
			
			if (pathCost > node.pathCost)
				return 1;
			
			return 0;
		}
		
		public String toString() {
			
			return state.toString();
		}
	}
	
	/**
	 * Performs a search using the A* search archetype.
	 * 
	 * @param start The starting state.
	 * @param goal The goal state to be found.
	 * @return A List of states representing the path taken to reach the node containing the goal state.
	 */
	public static List<StateWithHeuristic> solve(StateWithHeuristic start, StateWithHeuristic goal) {
		
		// Prioritized collection of nodes that have not been explored.
		PriorityQueueSet<Node> frontier = new PriorityQueueSet<>();
		// Collection (with fast search) holding nodes that have been explored.
		Set<StateWithHeuristic> explored = new HashSet<>();
		// Will hold the solution path, if found.
		List<StateWithHeuristic> solution = null;
		// The total number of nodes explored.
		int nodesExplored = 0;
		// The total number of nodes that have been in the frontier.
		int nodesInFrontier = 0;
		// The total number of nodes created.
		int nodesCreated = 0;
		// The best path.
		List<Node> bestPath = new LinkedList<Node>();
		
		
		Node node = new Node(start, null, goal, 0.0);
		frontier.add(node);
		bestPath.add(node);
		nodesInFrontier++;
		
		while (!frontier.isEmpty()) {
			
			node = frontier.remove();
			nodesExplored++;
						
			if (node.state.equals(goal)) {
				
				solution = constructSolutionPath(node);
				break;
				
			}
			
			explored.add(node.state);
			Map<? extends StateWithHeuristic,Double> neighbors = node.state.getNeighborsWithCost();
			

			System.out.println("\nViewing " + node.toString() + "(ECTG: " + node.state.getEstimatedCostToGoal(goal)+ ")" + " children:");
			
			for (StateWithHeuristic child : neighbors.keySet()) {
				
				nodesCreated++;
				
				if (!explored.contains(child)) {
					
					Double pathCost = node.trueCost + (node.state.getEstimatedCostToGoal(goal) - child.getEstimatedCostToGoal(goal));
					
					Node childNode = new Node(child, node, goal, pathCost);
					frontier.add(childNode);
					nodesInFrontier++;
					

					System.out.println("     " + childNode.toString() + ", trueCost: " + childNode.trueCost + ", ECTG: " + childNode.pathCost);
					
				}
			}
		}
		
		if (solution != null) {

			System.out.println("\n\n");
			
			for (StateWithCost state : solution)
				System.out.println(state.toString());
			
			System.out.println("Solution in " + (solution.size() - 1) + " moves.");
			System.out.println("Solution cost: " + node.trueCost);
			
		}
		
		System.out.println("   Nodes explored: " + nodesExplored);
		System.out.println("Nodes in frontier: " + nodesInFrontier);
		System.out.println("    Nodes created: " + nodesCreated);
		
		return solution;
		
	}
	
	private static List<StateWithHeuristic> constructSolutionPath(Node node) {
		
		LinkedList<StateWithHeuristic> path = new LinkedList<>();
		while (node != null) {
			path.addFirst(node.state);
			node = node.parent;
		}
		return path;
	}
}
